C++ Standard Library |
---|
Standard Template Library |
|
C standard library |
|
In computing, associative containers refer to a group of class templates in the standard library of the C++ programming language that implement ordered associative arrays.[1] Being templates, they can be used to store arbitrary elements, such as integers or custom classes. The following containers are defined in the current revision of the C++ standard: set
, map
, multiset
, multimap
. Each of these containers differ only on constraints placed on their elements.
The associative containers are similar to the unordered associative containers in C++ standard library, the only difference is that the unordered associative containers, as their name implies, do not order their elements.
Contents |
map
and set
each key must be unique. multimap
and multiset
do not have this restriction.map
and multimap
each element is composed from a key and a mapped value. In set
and multiset
each element is key; there are no mapped values.Associative containers are designed to be especially efficient in accessing its elements by their key, as opposed to sequence containers which are more efficient in accessing elements by their position.[1] Associative containers are guaranteed to perform operations of insertion, deletion, and testing whether an element is in it, in logarithmic time - O(log n). As such, they are typically implemented using self-balancing binary search trees and support bidirectional iteration. Iterators and references are not invalidated by insert and erase operations, except for iterators and references to erased elements.
The asymptotic complexity of the operations that can be applied to associative containers are as follows:
Operation | Complexity |
---|---|
Searching for an element | O(log n) |
Inserting a new element | O(log n) |
Incrementing/decrementing an iterator | O(log n) |
Removing a single element | O(log n) |
The containers are defined in headers named after the names of the containers, e.g. set
is defined in header <set>
. All containers satisfy the requirements of the Container concept, which means they have begin()
, end()
, size()
, max_size()
, empty()
, and swap()
methods.
set |
map |
multiset |
multimap |
Description | |
---|---|---|---|---|---|
(constructor) | (constructor) | (constructor) | (constructor) | Constructs the container from variety of sources | |
(destructor) | (destructor) | (destructor) | (destructor) | Destructs the set and the contained elements | |
operator= |
operator= |
operator= |
operator= |
Assigns values to the container | |
get_allocator |
get_allocator |
get_allocator |
get_allocator |
Returns the allocator used to allocate memory for the elements | |
Element access | N/A | at |
N/A | N/A | Accesses specified element with bounds checking. |
N/A | operator[] |
N/A | N/A | Accesses specified element without bounds checking. | |
Iterators | begin |
begin |
begin |
begin |
Returns an iterator to the beginning of the container |
end |
end |
end |
end |
Returns an iterator to the end of the container | |
rbegin |
rbegin |
rbegin |
rbegin |
Returns a reverse iterator to the reverse beginning of the container | |
rend |
rend |
rend |
rend |
Returns a reverse iterator to the reverse end of the container | |
Capacity | empty |
empty |
empty |
empty |
Checks whether the container is empty |
size |
size |
size |
size |
Returns number of elements in the container. | |
max_size |
max_size |
max_size |
max_size |
Returns the maximum possible number of elements in the container | |
Modifiers | clear |
clear |
clear |
clear |
Clears the contents. |
insert |
insert |
insert |
insert |
Inserts elements. | |
emplace |
emplace |
emplace |
emplace |
Constructs elements in-place (C++11) | |
emplace_hint |
emplace_hint |
emplace_hint |
emplace_hint |
Constructs elements in-place using a hint (C++11) | |
erase |
erase |
erase |
erase |
Erases elements. | |
swap |
swap |
swap |
swap |
Swaps the contents with another container. | |
Lookup | count |
count |
count |
count |
Returns the number of elements matching specific key. |
find |
find |
find |
find |
Finds an element with specific key. | |
equal_range |
equal_range |
equal_range |
equal_range |
Returns a range of elements matching specific key. | |
lower_bound |
lower_bound |
lower_bound |
lower_bound |
Returns an iterator to the first element with a key not less than the given value. | |
upper_bound |
upper_bound |
upper_bound |
upper_bound |
Returns an iterator to the first element with a key greater than a certain value. | |
Observers | key_comp |
key_comp |
key_comp |
key_comp |
Returns the key comparison function. |
value_comp |
value_comp |
value_comp |
value_comp |
Returns the value comparison function. In set and multiset this function isequivalent to key_comp , since the elements are composed from a key only. |
The following code demonstrates how to use the map<string, int>
to count occurrences of words. It uses the word as the key and the count as the value.
#include <iostream> #include <string> #include <map> int main() { std::map<std::string, int> wordcounts; std::string s; while (std::cin >> s && s != "end") ++wordcounts[s]; while (std::cin >> s && s != "end") std::cout << s << ' ' << wordcounts[s] << '\n'; }
When executed, the user first types a series of words separated by spaces, and a word "end" to signify the end of input; then the user can input words to query how many times each word occurred in the previous series.
The above example also demonstrates that the operator [] inserts new objects (using the default constructor) in the map if there isn't one associated with the key. So integral types are zero-initialized, strings are initialized to empty strings, etc.
The following example illustrates inserting elements into a map using the insert function and searching for a key using a map iterator and the find function:
#include <iostream> #include <map> #include <utility> // make_pair int main() { typedef std::map<char, int> MapType; MapType my_map; // insert elements using insert function my_map.insert(std::pair<char, int>('a', 1)); my_map.insert(std::pair<char, int>('b', 2)); my_map.insert(std::pair<char, int>('c', 3)); my_map.insert(MapType::value_type('d', 4)); // all standard containers provide this typedef my_map.insert(std::make_pair('e', 5)); // can also use the utility function make_pair my_map.insert({'f', 6}); // using C++11 initializer list //map keys are sorted automatically from lower to higher. //So, my_map.begin() points to the lowest key value not the key which was inserted first. MapType::iterator iter = my_map.begin(); // erase the first element using the erase function my_map.erase(iter); // output the size of the map std::cout << "Size of my_map: " << my_map.size() << '\n'; std::cout << "Enter a key to search for: "; char c; std::cin >> c; // find will return an iterator to the matching element if it is found // or to the end of the map if the key is not found iter = my_map.find(c); if (iter != my_map.end() ) std::cout << "Value is: " << iter->second << '\n'; else std::cout << "Key is not in my_map" << '\n'; // clear the entries in the map my_map.clear(); }
In the above example, five elements are entered using the insertion function, and then the first element is deleted. Then, the size of the map is output. Next, the user is prompted for a key to search for. Using the iterator, the find function searches for an element with the given key. If it finds the key, the program prints the element's value. If it does not find it, an iterator to the end of the map is returned and it outputs that the key could not be found. Finally all the elements in the tree are erased.
Maps may use iterators to point to specific elements in the container. An iterator can access both the key and the mapped value of an element:[1]
map<Key,T>::iterator it; // declares a map iterator it->first; // the key value it->second; // the mapped value (*it); // the "element value", which is of type: pair<const Key,T>
Below is an example of looping through a map to display all keys and values using iterators:
#include <iostream> #include <string> #include <map> int main() { typedef std::map <std::string, int> MapType; MapType data; // let's declare some initial values to this map data["Bobs score"] = 10; data["Martys score"] = 15; data["Mehmets score"] = 34; data["Rockys score"] = 22; data["Rockys score"] = 23; /*overwrites the 22 as keys are unique */ // Iterate over the map and print out all key/value pairs. // Using a const_iterator since we are not going to change the values. MapType::const_iterator end = data.end(); for (MapType::const_iterator it = data.begin(); it != end; ++it) { std::cout << "Who(key = first): " << it->first; std::cout << " Score(value = second): " << it->second << '\n'; } return 0; }
This will output the keys and values of the entire map, sorted by keys.